home *** CD-ROM | disk | FTP | other *** search
/ C & C++ Multimedia Cyber Classroom / C and C++ Multimedia Cyber Classroom (Prentice Hall) (1998).iso / src / fig20_40.jar / Ch20 / Fig20_40 / fig20_40.cpp next >
C/C++ Source or Header  |  1997-11-11  |  1KB  |  54 lines
  1. // Fig. 20.40: fig20_40.cpp                                
  2. // Using a bitset to demonstrate the Sieve of Eratosthenes.
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <bitset>
  6. #include <cmath>
  7.  
  8. using namespace std;
  9.  
  10. int main()
  11. {
  12.    const int size = 1024;
  13.    int i, value, counter;
  14.    bitset< size > sieve;
  15.  
  16.    sieve.flip();
  17.  
  18.    // perform Sieve of Eratosthenes
  19.    int finalBit = sqrt( sieve.size() ) + 1;
  20.  
  21.    for ( i = 2; i < finalBit; ++i ) 
  22.       if ( sieve.test( i ) ) 
  23.          for ( int j = 2 * i; j < size; j += i ) 
  24.             sieve.reset( j );
  25.  
  26.    cout << "The prime numbers in the range 2 to 1023 are:\n";
  27.  
  28.    for ( i = 2, counter = 0; i < size; ++i )
  29.       if ( sieve.test( i ) ) {
  30.          cout << setw( 5 ) << i;
  31.  
  32.          if ( ++counter % 12 == 0 ) 
  33.             cout << '\n';
  34.       }            
  35.    
  36.    cout << endl;
  37.  
  38.    // get a value from the user to determine if it is prime
  39.    cout << "\nEnter a value from 1 to 1023 (-1 to end): ";
  40.    cin >> value;
  41.  
  42.    while ( value != -1 ) {
  43.       if ( sieve[ value ] )
  44.          cout << value << " is a prime number\n";
  45.       else
  46.          cout << value << " is not a prime number\n";
  47.       
  48.       cout << "\nEnter a value from 2 to 1023 (-1 to end): ";
  49.       cin >> value;
  50.    }
  51.  
  52.    return 0;
  53. }
  54.